class Solution {
public:
    int trap(vector<int>& height) {
        int leftWall = 0, rightWall = leftWall+1;
        int waterTraped = 0;
        while(leftWall < height.size()){
            rightWall = RightHigherWall(height, leftWall);
            waterTraped += CalWaterTraped(height, leftWall, rightWall);
            leftWall = rightWall;
        }
        return waterTraped;
    }
    int RightHigherWall(vector<int>& height, int leftWall){
        int wallNums = height.size();
        int leftWallHeight = height[leftWall];//起始的墙，第一类:起始墙>后面墙，第二类:起始墙<=后面墙
        int checkWallIdx = leftWall+1;//向右迭代检测的墙编号
        int checkHighestWallIdx = checkWallIdx; //用来判断右边最高的墙编号
        while(checkWallIdx < wallNums){
            if(leftWallHeight <= height[checkWallIdx]){
                return checkWallIdx;
            }else if(height[checkHighestWallIdx] <= height[checkWallIdx]){
                checkHighestWallIdx = checkWallIdx;
            }
            checkWallIdx += 1;
        }
        return checkHighestWallIdx;
    }
    int CalWaterTraped(vector<int>& height, int leftWall, int rightWall){
        int leftWallHeight = height[leftWall];
        int rightWallHeight = height[rightWall];
        int checkHeight = leftWallHeight < rightWallHeight ? leftWallHeight : rightWallHeight;
        int i, trapedWater = 0;
        for(i = leftWall+1; i < rightWall; ++i){
            trapedWater += checkHeight - height[i];
        }
        return trapedWater;
    }
};